'''
n 比较小的时候，可以直接使用过递归法求解，不做任何记忆化操作，时间复杂度是 O(2^n))，存在很多冗余计算。
一般情况下，我们使用「记忆化搜索」或者「迭代」的方法，实现这个转移方程，时间复杂度和空间复杂度都可以做到 O(n)O(n)。
为了优化空间复杂度，我们可以不用保存 f(x - 2) 之前的项，我们只用三个变量来维护 f(x)、f(x−1)和f(x−2)，你可以理解成是把「滚动数组思想」应用在了动态规划中，也可以理解成是一种递推，这样把空间复杂度优化到了 O(1)O(1)。
随着 n的不断增大 O(n) 可能已经不能满足我们的需要了，我们可以用「矩阵快速幂」的方法把算法加速到 O(logn)。
我们也可以把 nn 代入斐波那契数列的通项公式计算结果，但是如果我们用浮点数计算来实现，可能会产生精度误差。
'''
import math

# 典型的简单动态规划问题。其实它好像是个斐波那契数列
def climbStairs(self, n: int) -> int:
    # 动态规划，迭代求解
    res = [1, 2]  # 一层,两层
    if n <= 2:
        return res[n - 1]
    for i in range(2, n):
        res.append(res[i - 1] + res[i - 2])
    return res[n - 1]

# 考虑优化内存
def climbStairs(n):
    a = 0
    b = 1
    for i in range(1, n + 1):
        a, b = b, a + b
    return b

# 采用数学方式，推出斐波那契数列的公式
def climbStairs(n):
    sqrt5 = math.sqrt(5)
    fibn = math.pow((1 + sqrt5) / 2, n + 1) - math.pow((1 - sqrt5) / 2, n + 1)
    return int(round(fibn / sqrt5))